/**
 * @author 03010570
 * @date 2020/07/17
 * describe:    LeetCode :34、在排序数组中查找元素的第一个值和最后一个值  https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 */
public class LeetCode_34 {
    public static void main(String[] args) {
        int[] ints = {2,2};
        int[] ints1 = searchRange(ints, 3);
        for (int i : ints1) {
            System.out.print(i + " ,");
        }
    }

    public static int[] searchRange(int[] nums, int target) {
        int[] res = new int[2];
        res[0] = -1;
        res[1] = -1;
        if(nums.length == 0){
            return res;
        }
        // 查找第一个等于给定值的元素

        int start = 0;
        int end = nums.length-1;
        while (start <= end) {
            int middle = start + ((end - start) >> 1);
            if (nums[middle] > target) {
                end = middle - 1;
            } else if (nums[middle] < target) {
                start = middle + 1;
            } else {
                if (middle == 0 || nums[middle - 1] != target) {
                    res[0] = middle;
                    break;
                } else end = middle - 1;
            }
        }
        start = 0;
        end = nums.length-1;
        while (start <= end) {
            int middle = start + ((end - start) >> 1);
            if (nums[middle] > target) {
                end = middle - 1;
            } else if (nums[middle] < target) {
                start = middle + 1;
            } else {
                if (middle == (nums.length - 1) || nums[middle + 1] != target) {
                    res[1] = middle;
                    break;
                } else start = middle + 1;
            }
        }
        return res;
    }
}
